The skip-connections used in residual networks have become a standard architecture choice in deep learning due to the increased generalization and stability of networks with this architecture, although there have been limited theoretical guarantees for this improved performance. In this work, we analyze overparameterized deep residual networks trained by gradient descent following random initialization, and demonstrate that (i) the class of networks learned by gradient descent constitutes a small subset of the entire neural network function class, and (ii) this subclass of networks is sufficiently large to guarantee small training error. By showing (i) we are able to demonstrate that deep residual networks trained with gradient descent have a small generalization gap between training and test error, and together with (ii) this guarantees that the test error will be small. Our optimization and generalization guarantees require overparameterization that is only logarithmic in the depth of the network, which helps explain why residual networks are preferable to fully connected ones.

The paper describes the proof for characterizing the fully connected deep ReLU residual network's optimization and generalization properties, trained with gradient descent following Gaussian initialization.Building on the work from [5] the authors demonstrate that over-parameterization forces gradient descent-trained networks to stay in a small neighborhood of initialization where the learned networks are guaranteed to find small surrogate training error, and come from a sufficiently small hypothesis class to guarantee a small generalization gap between the training and test errors. This allows for derivation of test error guarantees. The proof's show that provided we have sufficient overparameterization, gradient descent is guaranteed to find networks that have arbitrarily high classification accuracy. In comparison with the results of Cao and Gu [5], the width m, number of samples n, step size η, and number of iterates K required for the guarantees for residual networks given in Theorem 3.5 and Corollary 3.7 all have (at most) logarithmic dependence on L. Additionally, the step size and number of iterations required for our guarantees are independent of the depth. Finally, the presence of skip connections in the network architecture removes the complications relating to the depth that traditionally arise in the analysis of non-residual architectures, and provides an explanation for why residual networks can be trained easily at all depths, unlike non-residual ones.

The paper derives generalization bounds for overparametrized deep residual networks learned by gradient descent from random initialization. All reviewers appreciate the importance of the topic of the paper. However, R1 and R3 feel that the contribution is too close to prior art, including [5] [24] and another NeurIPS submission. On the other hand, R2 thinks that the contributions relative to prior art are meaningful and vouches for acceptance. The rebuttal successfully addresses the differences: [24] focuses on optimization with squared loss, while this submission focuses on generalization with cross entropy loss. The Wide and Deep paper focuses on optimization and generalization for fully connected networks trained by SGD, while this paper focuses on residual networks trained with gradient descent.

The skip-connections used in residual networks have become a standard architecture choice in deep learning due to the increased generalization and stability of networks with this architecture, although there have been limited theoretical guarantees for this improved performance. In this work, we analyze overparameterized deep residual networks trained by gradient descent following random initialization, and demonstrate that (i) the class of networks learned by gradient descent constitutes a small subset of the entire neural network function class, and (ii) this subclass of networks is sufficiently large to guarantee small training error. By showing (i) we are able to demonstrate that deep residual networks trained with gradient descent have a small generalization gap between training and test error, and together with (ii) this guarantees that the test error will be small. Our optimization and generalization guarantees require overparameterization that is only logarithmic in the depth of the network, which helps explain why residual networks are preferable to fully connected ones.

The skip-connections used in residual networks have become a standard architecture choice in deep learning due to the increased generalization and stability of networks with this architecture, although there have been limited theoretical guarantees for this improved performance. In this work, we analyze overparameterized deep residual networks trained by gradient descent following random initialization, and demonstrate that (i) the class of networks learned by gradient descent constitutes a small subset of the entire neural network function class, and (ii) this subclass of networks is sufficiently large to guarantee small training error. By showing (i) we are able to demonstrate that deep residual networks trained with gradient descent have a small generalization gap between training and test error, and together with (ii) this guarantees that the test error will be small. Our optimization and generalization guarantees require overparameterization that is only logarithmic in the depth of the network, which helps explain why residual networks are preferable to fully connected ones. Papers published at the Neural Information Processing Systems Conference.